import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        int[] nums = new int[]{1,2,5};
        System.out.println(test.canPartition(nums));
    }

    public boolean canPartition(int[] nums) {
        /**
         * 分割等和子集
         * 状态表示：
         *  dp[i][j]表示以i下标元素为结尾的数组中挑出一些元素 使得其和恰好等于j 此时的最大长度
         * 状态转移方程：
         *  dp[i][j] = dp[i-1][j];
         *  if(j >= nums[i-1]) {
         *      dp[i][j] = dp[i-1][j-nums[i-1]] + 1;
         *  }
         * 初始化：
         *  无需初始化
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return dp[m][n];
         * 错了一次，主要是因为我写成了不超过x的最大值，而不是等于x的最大值
         * */
        // 1 预处理
        int total = Arrays.stream(nums).sum();
        if(total % 2 == 1) {
            return false;
        }
        int t = total / 2;
        int n = nums.length;
        // 2 创建dp表
        int[][] dp = new int[n+1][t+1];
        // 3 初始化（无需初始化）
        // 4 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= t; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1] && (j == nums[i-1] || dp[i-1][j-nums[i-1]] != 0)) {
                    dp[i][j] = dp[i-1][j-nums[i-1]] + 1;
                }
            }
        }
        // 5 返回值
        return dp[n][t] > 0;
    }
}

